Many users of global positioning system (GPS) devices upload their GPS data (tracks) to the Internet, sometimes in conjunction with photographs and the like, such as for browsing and sharing travel and other experiences. In addition to sharing with others, users that upload their GPS tracks may benefit by having a better record of past events, which helps in reliving past events and gaining an understanding of their life patterns.
However, as more and more GPS logs are accumulated, managing and indexing the GPS data is becoming an important issue for Web applications/sites that provide the upload and retrieval service. In addition to storage considerations, users also need an efficient way to retrieve the specific GPS tracks in which they are interested. Existing search methods use text searches and tags, such as activity tags and region tags, but in general these methods are inadequate with respect to satisfying users' needs.
Attempts have been made to provide spatio-temporal search functionality to allow users to retrieve trajectories within a given spatial range over maps and a temporal interval. However, known spatio-temporal indexing schemes, such as an R-tree or its variants, are not configured particularly well with respect to handling the skewed nature of accumulated GPS tracks.